/*
 * @Author: your name
 * @Date: 2021-06-22 23:18:02
 * @LastEditTime: 2021-06-23 00:16:12
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \leetcode\322.cpp
 */
#include "leetcode-definition.h"
/*
 * @lc app=leetcode.cn id=322 lang=cpp
 *
 * [322] 零钱兑换
 */

// @lc code=start
class Solution {
public:
int dp(vector<int>&coins,int amount,vector<int>& dptable)
{
    if(dptable[amount]!=INT_MAX)
    return dptable[amount];
    if(amount==0)
    return 0;
    if(amount<0)
    return -1;

    int minSolu=INT_MAX;
        for (auto coin:coins)
        {
                int res = dp(coins,amount-coin,dptable);

                if(res!=-1)
                    if(minSolu>res+1)
                    minSolu=res+1;
        }
        
        if(minSolu!=INT_MAX)
        {
            dptable[amount]=minSolu;
            return minSolu;
        }
        else return -1;
}
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dptable(amount+1,INT_MAX);
            return  dp(coins,amount,dptable);
    }
};
class Solution2 {
public:

    int coinChange(vector<int>& coins, int amount) {
        vector<long int> dptable(amount+1,INT_MAX);
        dptable[0]=0;
        for(auto coin :coins)
        {
            for (int i =0;i<=amount;++i)
            {
                if(coin<=i)
                    dptable[i]=min(dptable[i],dptable[i-coin]+1);
            }
        }

            return  dptable[amount]==INT_MAX?-1:dptable[amount];
    }
};


// @lc code=end

